package tree.binarySortTree;

import java.util.HashMap;
import java.util.Map;

public class BinarySortTreeDemo {
	public static void main(String[] args) {
		int[] array = {7, 3, 10, 12, 5, 1, 9, 2};
		BinarySortTree binarySortTree = new BinarySortTree();
		//循环添加节点
		for (int i = 0; i < array.length; i++) {
			binarySortTree.addNode(new Node(array[i]));
		}

		//中序遍历
		System.out.println("中序遍历");
		binarySortTree.infixOrder();

		int val = 111111;
		//查找待删除节点
		Map<String, Node> nodes = binarySortTree.search(val);
		System.out.println(nodes);

		//删除
		binarySortTree.delNode(111111);
//        binarySortTree.delNode(5);
//        binarySortTree.delNode(9);
//        binarySortTree.delNode(7);
//        binarySortTree.delNode(3);
//        binarySortTree.delNode(1);
//        binarySortTree.delNode(10);
//        binarySortTree.delNode(12);

		System.out.println("删除后");
		binarySortTree.infixOrder();
	}

}

//创建二叉排序树
class BinarySortTree {
	private Node root;

	public Node getRoot() {
		return root;
	}

	//查找待删除的节点
	public Map<String, Node> search(int val) {
		if (this == null) {
			System.out.println("节点为空");
		}
		Map<String, Node> nodes = root.search(val);
		return nodes;
	}

	//删除节点
	public void delNode(int val) {
		if (root == null) {
			return;
		} else {
			Map<String, Node> nodes = root.search(val);

			//    如果没要找到
			if (nodes == null) {
				System.out.println("待删除节点不存在");
				return;
			}
			// 1. 先找到要删除的节点
			Node targetNode = nodes.get("targetNode");

			// 2. 查找 targetNode 父节点
			Node parentNode = nodes.get("parentNode");
			// 3. 如果要删除的是叶子节点
			if (targetNode.left == null && targetNode.right == null) {
				if (parentNode == null) {
					root = null;
					return;
				}
				//判断 targetNode 是 parentNode 的左子节点还是右子节点
				if (parentNode.left != null && parentNode.left.val == val) {
					parentNode.left = null;
				} else if (parentNode.right != null && parentNode.right.val == val) {
					parentNode.right = null;
				}
			} else if (targetNode.left != null && targetNode.right != null) {
				//targetNode 同时有左右子树
				//思路 1. 从 targetNode 的 右 子树中找到最 小 的节点，删除该节点，并把值赋给 targetNode
				//思路 2. 从 targetNode 的 左 子树中找到最 大 的节点，删除该节点，并把值赋给 targetNode

				int minVal = delRightTreeMin(targetNode.right);
				targetNode.val = minVal;

			} else {
				if (targetNode.left != null) {
					//targetNode 只有左子树
					if (parentNode == null) {
						root = targetNode.left;
						return;
					}
					if (parentNode.left.val == val) {
						//如果 targetNode 是 parentNode 的左子节点
						parentNode.left = targetNode.left;
					} else {
						//如果 targetNode 是 parentNode 的右子节点
						parentNode.right = targetNode.left;
					}
				} else {
					//targetNode 只有右子树
					if (parentNode == null) {
						root = targetNode.right;
						return;
					}
					if (parentNode.left.val == val) {
						//如果 targetNode 是 parentNode 的左子节点
						parentNode.left = targetNode.right;
					} else {
						//如果 targetNode 是 parentNode 的右子节点
						parentNode.right = targetNode.right;
					}
				}
			}


		}
	}

	/**
	 * 1.返回以node为根节点的二叉排序树中的最小节点
	 * 2.删除上面的最小的节点
	 *
	 * @param node 传入的节点，当作二叉排序树的根节点
	 * @return 返回以node为根节点的二叉排序树中的最小节点
	 */
	public int delRightTreeMin(Node node) {
		Node temp = node;
		//循环的查找左节点，找最小值
		while (temp.left != null) {
			temp = temp.left;
		}
		//temp 指向了最小的节点,并删除
		delNode(temp.val);

		return temp.val;
	}

	//添加节点
	public void addNode(Node node) {
		if (root == null) {
			//为空树
			root = node;
		} else {
			root.addNode(node);
		}
	}


	//中序遍历
	public void infixOrder() {
		if (root != null) {
			root.infixOrder();
			System.out.println();
		} else {
			System.out.println("树为空");
		}
	}


}


class Node {
	int val;
	Node left;
	Node right;

	Node(int x) {
		val = x;
	}

	@Override
	public String toString() {
		return "Node{" +
				"val=" + val +
				'}';
	}


	//查找要删除的节点
	public Map<String, Node> search(int val) {
		Map<String, Node> nodes = new HashMap<>();
		if (val == this.val) {
			//若满足，则找到
			nodes.put("parentNode", null);
			nodes.put("targetNode", this);
			return nodes;
		} else if (this.left != null && val == this.left.val) {
			//若满足，则找到
			nodes.put("parentNode", this);
			nodes.put("targetNode", this.left);
			return nodes;
		} else if (this.right != null && val == this.right.val) {
			//若满足，则找到
			nodes.put("parentNode", this);
			nodes.put("targetNode", this.right);
			return nodes;
		} else if (this.left != null && val < this.val) {
			//查找的值小于当前值，则向左子树递归查找
			return this.left.search(val);
		} else if (this.right != null && val >= this.val) {
			return this.right.search(val);
		} else {
			return null;
		}
	}


	//添加节点
	public void addNode(Node node) {
		if (node == null) {
			return;
		}

		//判断传入的节点的值，和当前子树的根节点的值的关系
		if (node.val < this.val) {
			if (this.left == null) {
				//若当前节点，左子节点为空
				this.left = node;
			} else {
				//若不为空，递归
				this.left.addNode(node);
			}
		} else {
			if (this.right == null) {
				//若当前节点，左子节点为空
				this.right = node;
			} else {
				//若不为空，递归
				this.right.addNode(node);
			}
		}
	}

	//中序遍历
	public void infixOrder() {
		if (this.left != null) {
			this.left.infixOrder();
		}
		System.out.print(this.val + "  ");
		if (this.right != null) {
			this.right.infixOrder();
		}
	}
}

